﻿#include"head.h"

//打印路径
void printPath(int parent[], int j, char data[]) {
    if (parent[j] == -1) {
        printf("%c", data[j]);
        return;
    }
    printPath(parent, parent[j], data);
    printf(" -> %c", data[j]);
}

//打印最短路径距离和路径
void printSolution(int dist[], int parent[], char data[]) {
    printf("顶点\t距离源点\t路径\n");
    for (int i = 0; i < V; i++) {
        printf("%c\t%d\t\t", data[i], dist[i]);
        printPath(parent, i, data);
        printf("\n");
    }
}

//选择未处理的顶点中距离最小的
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX;
    int min_index;
    for (int v = 0; v < V; v++) {
        if (sptSet[v] == 0 && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

//迪杰斯特拉算法
void dijkstra(int graph[V][V], int src, char data[]) {
    int dist[V];  //从源点到各顶点的距离
    int sptSet[V];  //记录哪些顶点已经处理过
    int parent[V];  //记录前驱节点
    //初始化距离和集合
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
        parent[i] = -1;
    }
    //源点的距离设为0
    dist[src] = 0;
    //遍历所有顶点
    for (int count = 0; count < V - 1; count++) {
        //选择未处理的顶点中距离最小的
        int u = minDistance(dist, sptSet);
        //将选中的顶点标记为处理过
        sptSet[u] = 1;
        //更新与u相邻的顶点的距离
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;  //更新前驱节点
            }
        }
    }
    //打印结果
    printSolution(dist, parent, data);
}
